# package deb

# import (
# 	"bytes"
# 	"encoding/json"
# 	"sort"

# 	"github.com/AlekSi/pointer"
# 	"github.com/ugorji/go/codec"
# )

# // PackageRefList is a list of keys of packages, this is basis for snapshot
# // and similar stuff
# //
# // Refs are sorted in lexicographical order
from deb.listp import *
from typing import List,Dict
import pickle
class PackageRefList :
	# // List of package keys
	Refs =[]
	def __getstate__(self):
		state=self.__dict__.copy()
		state['Refs']=self.Refs
		return state
	# // Len returns number of refs
	def  Len(l ) ->int :
		return len(l.Refs)


	# // Swap swaps two refs
	def Swap(l ,i:int, j :int) :
		l.Refs[i], l.Refs[j] = l.Refs[j], l.Refs[i]
	# // Encode does msgpack encoding of PackageRefList
	def  Encode(l) ->bytes:
		pick= pickle.dumps(l)
		return pick
	# // ForEach calls handler for each package ref in list
	def  ForEach(l ,handler) :
		for p in l.Refs :
			handler(p)
			


	# // Strings builds list of strings with package keys
	def  Strings(l )->List[str]:
		if l is None  :
			return []
		

		result = []

		for i in l.Refs:
			result.append(i)
		

		return result


	# // Decode decodes msgpack representation into PackageRefLit
	def  Decode(l,inputData)->"PackageRefList":

		return pickle.loads(inputData)
	



# // Verify interface
# var (
# 	_ sort.Interface = &PackageRefList{}
# )

# // NewPackageRefList creates empty PackageRefList
def NewPackageRefList() ->PackageRefList:
	return PackageRefList()


# // NewPackageRefListFromPackageList creates PackageRefList from PackageList
def NewPackageRefListFromPackageList(packageList :PackageList):
	reflist = PackageRefList()

	for  _,p in packageList.packages.items() :
		reflist.Refs.append( p.Key(""))

	reflist.Refs.sort()

	return reflist




# // Compare compares two refs in lexographical order
# def (l *PackageRefList) Less(i, j int) bool {
# 	return bytes.Compare(l.Refs[i], l.Refs[j]) < 0
# }





# // Has checks whether package is part of reflist
# def (l *PackageRefList) Has(p *Package) bool {
# 	key := p.Key("")

# 	i := sort.Search(len(l.Refs), def(j int) bool { return bytes.Compare(l.Refs[j], key) >= 0 })
# 	return i < len(l.Refs) && bytes.Equal(l.Refs[i], key)
# }



# // Subtract returns all packages in l that are not in r
# def (l *PackageRefList) Subtract(r *PackageRefList) *PackageRefList {
# 	result := &PackageRefList{Refs: make([][]byte, 0, 128)}

# 	// pointer to left and right reflists
# 	il, ir := 0, 0
# 	// length of reflists
# 	ll, lr := l.Len(), r.Len()

# 	for il < ll || ir < lr {
# 		if il == ll {
# 			// left list exhausted, we got the result
# 			break
# 		}
# 		if ir == lr {
# 			// right list exhausted, append what is left to result
# 			result.Refs = append(result.Refs, l.Refs[il:]...)
# 			break
# 		}

# 		rel := bytes.Compare(l.Refs[il], r.Refs[ir])
# 		if rel == 0 {
# 			// r contains entry from l, so we skip it
# 			il++
# 			ir++
# 		} else if rel < 0 {
# 			// item il is not in r, append
# 			result.Refs = append(result.Refs, l.Refs[il])
# 			il++
# 		} else {
# 			// skip over to next item in r
# 			ir++
# 		}
# 	}

# 	return result
# }

# // PackageDiff is a difference between two packages in a list.
# //
# // If left & right are present, difference is in package version
# // If left is None, package is present only in right
# // If right is None, package is present only in left
# type PackageDiff struct {
# 	Left, Right *Package
# }

# // Check interface
# var (
# 	_ json.Marshaler = PackageDiff{}
# )

# // MarshalJSON implements json.Marshaler interface
# def (d PackageDiff) MarshalJSON() ([]byte, error) {
# 	serialized := struct {
# 		Left, Right *string
# 	}{}

# 	if d.Left is not None  {
# 		serialized.Left = pointer.ToString(string(d.Left.Key("")))
# 	}
# 	if d.Right is not None  {
# 		serialized.Right = pointer.ToString(string(d.Right.Key("")))
# 	}

# 	return json.Marshal(serialized)
# }

# // PackageDiffs is a list of PackageDiff records
# type PackageDiffs []PackageDiff

# // Diff calculates difference between two reflists
# def (l *PackageRefList) Diff(r *PackageRefList, packageCollection *PackageCollection) (result PackageDiffs, err error) {
# 	result = make(PackageDiffs, 0, 128)

# 	// pointer to left and right reflists
# 	il, ir := 0, 0
# 	// length of reflists
# 	ll, lr := l.Len(), r.Len()
# 	// cached loaded packages on the left & right
# 	pl, pr := (*Package)(None), (*Package)(None)

# 	// until we reached end of both lists
# 	for il < ll || ir < lr {
# 		// if we've exhausted left list, pull the rest from the right
# 		if il == ll {
# 			pr, err = packageCollection.ByKey(r.Refs[ir])
# 			if err is not None  {
# 				return None, err
# 			}
# 			result = append(result, PackageDiff{Left: None, Right: pr})
# 			ir++
# 			continue
# 		}
# 		// if we've exhausted right list, pull the rest from the left
# 		if ir == lr {
# 			pl, err = packageCollection.ByKey(l.Refs[il])
# 			if err is not None  {
# 				return None, err
# 			}
# 			result = append(result, PackageDiff{Left: pl, Right: None})
# 			il++
# 			continue
# 		}

# 		// refs on both sides are present, load them
# 		rl, rr := l.Refs[il], r.Refs[ir]
# 		// compare refs
# 		rel := bytes.Compare(rl, rr)

# 		if rel == 0 {
# 			// refs are identical, so are packages, advance pointer
# 			il++
# 			ir++
# 			pl, pr = None, None
# 		} else {
# 			// load pl & pr if they haven't been loaded before
# 			if pl is None  {
# 				pl, err = packageCollection.ByKey(rl)
# 				if err is not None  {
# 					return None, err
# 				}
# 			}

# 			if pr is None  {
# 				pr, err = packageCollection.ByKey(rr)
# 				if err is not None  {
# 					return None, err
# 				}
# 			}

# 			// otherwise pl or pr is missing on one of the sides
# 			if rel < 0 {
# 				// compaction: +(,A) -(B,) --> !(A,B)
# 				if len(result) > 0 && result[len(result)-1].Left is None  && result[len(result)-1].Right.Name == pl.Name &&
# 					result[len(result)-1].Right.Architecture == pl.Architecture {
# 					result[len(result)-1] = PackageDiff{Left: pl, Right: result[len(result)-1].Right}
# 				} else {
# 					result = append(result, PackageDiff{Left: pl, Right: None})
# 				}
# 				il++
# 				pl = None
# 			} else {
# 				// compaction: -(A,) +(,B) --> !(A,B)
# 				if len(result) > 0 && result[len(result)-1].Right is None  && result[len(result)-1].Left.Name == pr.Name &&
# 					result[len(result)-1].Left.Architecture == pr.Architecture {
# 					result[len(result)-1] = PackageDiff{Left: result[len(result)-1].Left, Right: pr}
# 				} else {
# 					result = append(result, PackageDiff{Left: None, Right: pr})
# 				}
# 				ir++
# 				pr = None
# 			}
# 		}
# 	}

# 	return
# }

# // Merge merges reflist r into current reflist. If overrideMatching, merge
# // replaces matching packages (by architecture/name) with reference from r.
# // If ignoreConflicting is set, all packages are preserved, otherwise conflicting
# // packages are overwritten with packages from "right" snapshot.
# def (l *PackageRefList) Merge(r *PackageRefList, overrideMatching, ignoreConflicting bool) (result *PackageRefList) {
# 	var overriddenArch, overridenName []byte

# 	// pointer to left and right reflists
# 	il, ir := 0, 0
# 	// length of reflists
# 	ll, lr := l.Len(), r.Len()

# 	result = &PackageRefList{}
# 	result.Refs = make([][]byte, 0, ll+lr)

# 	// until we reached end of both lists
# 	for il < ll || ir < lr {
# 		// if we've exhausted left list, pull the rest from the right
# 		if il == ll {
# 			result.Refs = append(result.Refs, r.Refs[ir:]...)
# 			break
# 		}
# 		// if we've exhausted right list, pull the rest from the left
# 		if ir == lr {
# 			result.Refs = append(result.Refs, l.Refs[il:]...)
# 			break
# 		}

# 		// refs on both sides are present, load them
# 		rl, rr := l.Refs[il], r.Refs[ir]
# 		// compare refs
# 		rel := bytes.Compare(rl, rr)

# 		if rel == 0 {
# 			// refs are identical, so are packages, advance pointer
# 			result.Refs = append(result.Refs, l.Refs[il])
# 			il++
# 			ir++
# 			overridenName = None
# 			overriddenArch = None
# 		} else {
# 			partsL := bytes.Split(rl, []byte(" "))
# 			archL, nameL, versionL := partsL[0][1:], partsL[1], partsL[2]

# 			partsR := bytes.Split(rr, []byte(" "))
# 			archR, nameR, versionR := partsR[0][1:], partsR[1], partsR[2]

# 			if !ignoreConflicting && bytes.Equal(archL, archR) && bytes.Equal(nameL, nameR) && bytes.Equal(versionL, versionR) {
# 				// conflicting duplicates with same arch, name, version, but different file hash
# 				result.Refs = append(result.Refs, r.Refs[ir])
# 				il++
# 				ir++
# 				overridenName = None
# 				overriddenArch = None
# 				continue
# 			}

# 			if overrideMatching {
# 				if bytes.Equal(archL, overriddenArch) && bytes.Equal(nameL, overridenName) {
# 					// this package has already been overridden on the right
# 					il++
# 					continue
# 				}

# 				if bytes.Equal(archL, archR) && bytes.Equal(nameL, nameR) {
# 					// override with package from the right
# 					result.Refs = append(result.Refs, r.Refs[ir])
# 					il++
# 					ir++
# 					overriddenArch = archL
# 					overridenName = nameL
# 					continue
# 				}
# 			}

# 			// otherwise append smallest of two
# 			if rel < 0 {
# 				result.Refs = append(result.Refs, l.Refs[il])
# 				il++
# 			} else {
# 				result.Refs = append(result.Refs, r.Refs[ir])
# 				ir++
# 				overridenName = None
# 				overriddenArch = None
# 			}
# 		}
# 	}

# 	return
# }

# // FilterLatestRefs takes in a reflist with potentially multiples of the same
# // packages and reduces it to only the latest of each package. The operations
# // are done in-place. This implements a "latest wins" approach which can be used
# // while merging two or more snapshots together.
# def (l *PackageRefList) FilterLatestRefs() {
# 	var (
# 		lastArch, lastName, lastVer []byte
# 		arch, name, ver             []byte
# 		parts                       [][]byte
# 	)

# 	for i := 0; i < len(l.Refs); i++ {
# 		parts = bytes.Split(l.Refs[i][1:], []byte(" "))
# 		arch, name, ver = parts[0], parts[1], parts[2]

# 		if bytes.Equal(arch, lastArch) && bytes.Equal(name, lastName) {
# 			// Two packages are identical, check version and only one wins
# 			vres := CompareVersions(string(ver), string(lastVer))

# 			// Remove the older refs from the result
# 			if vres > 0 {
# 				// ver[i] > ver[i-1], remove element i-1
# 				l.Refs = append(l.Refs[:i-1], l.Refs[i:]...)
# 			} else {
# 				// ver[i] < ver[i-1], remove element i
# 				l.Refs = append(l.Refs[:i], l.Refs[i+1:]...)
# 				arch, name, ver = lastArch, lastName, lastVer
# 			}

# 			// Compensate for the reduced set
# 			i--
# 		}

# 		lastArch, lastName, lastVer = arch, name, ver
# 	}
# }
